#include "binarytree.h"

// @ 根据前序遍历和中序遍历构造二叉树
// @ prev : 前序遍历
// @ mid : 中序遍历
// @ return : BinaryTree : 创建的二叉树的根节点
BinaryTree BuildBinaryTreeByPrevTraversal(QString prev, QString mid) {
    if (0 == prev.length()) {
        return nullptr;
    }
    BinaryTree root = (BinaryTree)malloc(sizeof(BinaryTreeNode));
    if (nullptr == root) {
        return nullptr;
    }
    root->val = prev.at(0).toLatin1();
    QString leftTree = mid.section(root->val, 0, 0);
    QString rightTree = mid.section(root->val, -1);
    root->lchild = BuildBinaryTreeByPrevTraversal(prev.mid(1).left(leftTree.length()), leftTree);
    root->rchild = BuildBinaryTreeByPrevTraversal(prev.right(rightTree.length()), rightTree);
    return root;
}

// @ 根据后序遍历和中序遍历构造二叉树
// @ post : 后序遍历
// @ mid : 中序遍历
// @ return : BinaryTree : 创建的二叉树的根节点
BinaryTree BuildBinaryTreeByPostTraversal(QString post, QString mid) {
    if (0 == post.length()) {
        return nullptr;
    }
    BinaryTree root = (BinaryTree)malloc(sizeof(BinaryTreeNode));
    if (nullptr == root) {
        return nullptr;
    }
    root->val = post.rbegin()->toLatin1();
    QString leftTree = mid.section(root->val, 0, 0);
    QString rightTree = mid.section(root->val, -1);
    root->lchild = BuildBinaryTreeByPostTraversal(post.left(leftTree.length()), leftTree);
    root->rchild = BuildBinaryTreeByPostTraversal(post.mid(0, post.length()-1).right(rightTree.length()), rightTree);
    return root;
}

// @ 通过前(后)序遍历和中序遍历创建二叉树
// @ other : QString : 前(后)序遍历
// @ mid : QString : 中序遍历
// @ isPrev : bool : 判定是否为前序遍历,若为true则为前序遍历,否则为后序遍历
// @ return : BinaryTree : 返回新创建的二叉树的根节点
BinaryTree BuildBinaryTreeByTraversal(QString other, QString mid, bool isPrev) {
    if (isPrev == true) {
        return BuildBinaryTreeByPrevTraversal(other, mid);
    }
    else {
        return BuildBinaryTreeByPostTraversal(other, mid);
    }
}

// @ 通过括号序列创建二叉树
// @ str : QString : 括号序列
// @ return : BinaryTree : 返回新创建的二叉树的根节点
BinaryTree BuildBinaryTreeByParentheses(QString str) {
    if (0 == str.length()) {
        return nullptr;
    }
//    if (str.at(0).toLatin1() == ' ') {
//        return nullptr;
//    }
    BinaryTree root = (BinaryTree)malloc(sizeof(BinaryTreeNode));
    root->val = str.at(0).toLatin1();
    str = str.mid(2, str.length() - 3);
    int parenthesesCnt = 0;
    QString leftTree = "", rightTree = "";
    for (int i = 0; i <= str.length(); i++) {
        if (i == str.length()) {
            leftTree = str;
            break;
        }
        if (str[i] == '(') {
            parenthesesCnt++;
        }
        else if (str[i] == ')') {
            parenthesesCnt--;
        }
        else if (str[i] == ',') {
            if (parenthesesCnt == 0) {
                leftTree = str.left(i);
                rightTree = str.right(str.length() - i - 1);
                break;
            }
        }
    }
    root->lchild = BuildBinaryTreeByParentheses(leftTree);
    root->rchild = BuildBinaryTreeByParentheses(rightTree);
    return root;
}

// @ 销毁树
// @ tree : BinaryTree : 要销毁的树
void DestoryTree(BinaryTree tree) {
    if (tree->lchild != nullptr) {
        DestoryTree(tree->lchild);
    }
    if (tree->rchild != nullptr) {
        DestoryTree(tree->rchild);
    }
    free(tree);
}

int max(int a, int b) { return a > b ? a : b; }

// 未柯里化的获得二叉树深度
int GetTreeHeight(BinaryTree tree, int height) {
    int x = height;
    if (tree->lchild != nullptr) {
        x = max(x, GetTreeHeight(tree->lchild, height + 1));
    }
    if (tree->rchild != nullptr) {
        x = max(x, GetTreeHeight(tree->rchild, height + 1));
    }
    return x;
}

// @ 获得二叉树的深度
// @ tree : BinaryTree : 二叉树
// @ return : int : 二叉树的深度
int GetTreeHeight(BinaryTree tree) {
    return GetTreeHeight(tree, 1);
}
